package algorithm.weightgraph;

public class MinHeap<Item extends Comparable> {

    private Item[] data;

    private int capacity;

    private int count;

    public MinHeap(int capacity) {
        this.capacity = capacity + 1;
        this.data = (Item[]) new Comparable[capacity+1];
        this.count = 0;
    }


    public void addItem(Item item) {
        data[++count] = item;
        shiftUp(count);
    }

    public Item exportMin() {
        Item min = data[1];
        data[1] = data[count--];
        shiftDown(1);
        return min;
    }


    private void shiftDown(Integer index) {
        int j = index * 2;
        while (j <= count) {
            if (j + 1 <= count && data[j + 1].compareTo(data[j]) < 0) {
                j = j + 1;
            }
            if (data[j].compareTo(data[index]) < 0) {
                swap(data, j, index);
                index = j;
            } else {
                break;
            }
        }
    }

    private void shiftUp(Integer index) {
        while (index > 1 && data[index / 2].compareTo(data[index]) > 0) {
            swap(data, index / 2, index);
            index = index / 2;
        }
    }


    public int getCount() {
        return count;
    }

    private void swap(Item[] arr, int i, int j) {
        Item tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}
